package ListNode;

import java.util.HashSet;
import java.util.Set;
import java.util.Stack;

public class StackTest {

    public boolean isCorrect(String str){
        Stack<Character> stack=new Stack<>();
        for(int i=0;i<str.length();i++){
            if(stack.empty()){
                stack.push(str.charAt(i));
                continue;
            }
            if(str.charAt(i)==')'&&stack.peek()=='('){
                stack.pop();
            }
            else if(str.charAt(i)=='}'&&stack.peek()=='{'){
                stack.pop();
            }else if(str.charAt(i)==']'&&stack.peek()=='['){
                stack.pop();
            }else{
                stack.push(str.charAt(i));
            }
        }
        return stack.empty();
    }
    //斐波那契数列
    public int getN(int n){
        if(n<=1)
            return n;
        return getN(n-2)+getN(n-1);
    }

    public int getN2(int n){
        int[] arr=new int[n];
        arr[0]=0;
        arr[1]=1;
        for(int i=2;i<n;i++){
            arr[i]=arr[i-1]+arr[i-2];
        }
        return arr[n];
    }
    //回文数列
    public boolean isPolidRome(String str,int start,int end){
        while(start<end){
            if(str.charAt(start++)!=str.charAt(end--)){
                return false;
            }
        }
        return true;
    }
    //最大回文长度
    public int getLongestPalindrome(String str,int n){
        if(n<2){
            return n;
        }
        int max=0;
        for(int i=0;i<n-1;i++){
            for(int j=i;j<n;j++){
                if (j - i < max)
                    continue;
                if(isPolidRome(str,i,j)){
                    max=Math.max(max,j-i+1);
                }
            }
        }
        return max;
    }

    //
    public int getNum(int[] a){
        int count=0;
        int res=0;
        for(int i=0;i<a.length;i++){
            for(int j=0;j<a.length;j++){
                if(a[i]==a[j]){
                    count++;
                }

            }
            if(count>a.length/2){
                res=a[i];
            }else{
                count=0;
            }
        }
        return res;
    }

    //找环 不利用第三方集合
    public ListNode getHuan(ListNode head){
        ListNode fast=head;
        ListNode slow=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(slow==fast){
                ListNode slow2=head;
                while(slow2!=slow){
                    slow=slow.next;
                    slow2=slow2.next;
                }
                return slow;
            }
        }

        return null;
    }
    //找环  利用集合
    public ListNode getHuan2(ListNode head){
        Set<ListNode> set=new HashSet<ListNode>();
        while(head!=null){
            if(!set.add(head))
                return head;
            head=head.next;
        }
        return null;
    }
    //最小路径
    public int getMin(int[][] matrix){
        if(matrix.length==0 || matrix[0].length==0 || matrix==null){
            return 0;
        }
        int rows=matrix.length;
        int cols=matrix[0].length;
        int[][] dp=new int[rows][cols];
        dp[0][0]=matrix[0][0];
        for(int j=1;j<cols;j++){
            dp[0][j]=dp[0][j-1]+matrix[0][j];
        }
        for(int i=1;i<rows;i++){
            dp[i][0]=dp[i-1][0]+matrix[i][0];
        }
        for(int i=1;i<rows;i++){
            for(int j=1;j<cols;j++){
                dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+matrix[i][j];
            }
        }
        return dp[rows-1][cols-1];
    }
    //有序数组合并
    public void merge(int a[],int n,int b[],int m){
        int i=n-1;
        int j=m-1;
        int index=m+n-1;
        while(i>=0&&j>=0)
            a[index--]=a[i]>b[j]?a[i--]:b[j--];
        while(index>=0)
            a[index--]=b[j--];
    }
    public static void main(String[] args){
      /*  Stack<Character> stack=new Stack<>();
        stack.push('(');
        char c=stack.peek();
        System.out.print(c+" "+stack.empty());*/
   /*   int[] a={1,2,3,2,4,2,5,2,3};
      int res=new StackTest().getNum(a);
      System.out.println(res);*/

    /*  String str="123";
      System.out.print(str.substring(0,1));
      System.out.print(str.charAt(3));*/

  /*  int a[][]={{1,3,5,9},{8,1,3,4},{5,0,6,1},{8,8,4,0}};
    System.out.print(new StackTest().getMin(a));*/

        int a[]=new int[10];
        a[0]=1;
        a[1]=2;
        a[2]=3;
        a[3]=4;
        int b[]=new int[10];
        b[0]=1;
        b[1]=1;
        b[2]=3;
        Array array=new Array();
        array.merge(a,4,b,3);
        for(int i=0;i<a.length;i++){
            System.out.print(a[i]+" ");
        }
    }
}
